package com.leetcode.study;

/**
 * https://leetcode.cn/problems/minimum-path-sum/description/
 * 
 * 最小路径和
 *
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 */
public class L64 {

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1, 3}, {1, 5, 1, 6}, {4, 2, 1, 9}};
        //int[][] grid = {{9}};

        System.out.println(minPathSum(grid));

    }


    /**
     * 状态定义：
     *
     * 设 dp 为大小 m × n矩阵，其中 dp[i][j]的值代表直到走到 (i,j)的最小路径和。
     * 转移方程：
     *
     * 题目要求，只能向右或向下走，换句话说，当前单元格 (i,j) 只能从左方单元格 (i−1,j)(i−1,j) 或上方单元格 (i,j−1) 走到，因此只需要考虑矩阵左边界和上边界。
     *
     * i == 0 && j == 0
     * D[i][j] = grid[i][j]
     *
     * 只能往右面走
     * i == 0 && j !=0
     * D[i][j] = grid[i][j] + D[i][j-1]
     *
     * 只能往下走
     * i != 0 && j == 0
     * D[i][j] = grid[i][j] + D[i-1][j]
     *
     * 当前 i != 0 && j !=0
     * D[i][j] = grid[i][j] + min(D[i-1][j], D[i][j-1])
     *
     * @param grid
     * @return
     */
    public static int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {

                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];

                }
                // 只能往右面走
                else if (i == 0 ) {
                    dp[i][j] = grid[i][j] + dp[i][j - 1];

                }
                // 只能往下走
                else if (j == 0) {
                    dp[i][j] = grid[i][j] + dp[i - 1][j];
                    
                }
                // 当前 i != 0 && j !=0
                else {
                    dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
                }

            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }


}
